﻿//
// System.Collections.Generic.MapEx
//
// Authors:
//  Sureshkumar T ([email]tsureshkumar@novell.com[/email])
//  Marek Safar ([email]marek.safar@gmail.com[/email])
//  Ankit Jain ([email]radical@corewars.org[/email])
//  David Waite ([email]mass@akuma.org[/email])
//  Juraj Skripsky ([email]js@hotfeet.ch[/email])
//
//
// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
// Copyright (C) 2005 David Waite
// Copyright (C) 2007 HotFeet GmbH (http://www.hotfeet.ch)
// Copyright (C) 2011 Xamarin Inc (http://www.xamarin.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Runtime.InteropServices;
using System.Diagnostics;

//
// HashPrimeNumbers.cs
//
// Author:
//   Sergey Chaban ([email]serge@wildwestsoftware.com[/email])
//
// Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
//
static class HashPrimeNumbers
{
    static readonly int[] primeTbl = {
            11,
            19,
            37,
            73,
            109,
            163,
            251,
            367,
            557,
            823,
            1237,
            1861,
            2777,
            4177,
            6247,
            9371,
            14057,
            21089,
            31627,
            47431,
            71143,
            106721,
            160073,
            240101,
            360163,
            540217,
            810343,
            1215497,
            1823231,
            2734867,
            4102283,
            6153409,
            9230113,
            13845163
        };


    //
    // Private static methods
    //
    public static bool TestPrime(int x)
    {
        if ((x & 1) != 0)
        {
            int top = (int)Math.Sqrt(x);

            for (int n = 3; n < top; n += 2)
            {
                if ((x % n) == 0)
                    return false;
            }
            return true;
        }
        // There is only one even prime - 2.
        return (x == 2);
    }

    public static int CalcPrime(int x)
    {
        for (int i = (x & (~1)) - 1; i < Int32.MaxValue; i += 2)
        {
            if (TestPrime(i)) return i;
        }
        return x;
    }

    public static int ToPrime(int x)
    {
        for (int i = 0; i < primeTbl.Length; i++)
        {
            if (x <= primeTbl[i])
                return primeTbl[i];
        }
        return CalcPrime(x);
    }

}

//
// CollectionDebuggerView.cs
//
// Authors:
//  Marek Safar  <[email]marek.safar@gmail.com[/email]>
//
// Copyright (C) 2009 Novell, Inc (http://www.novell.com)
//
internal sealed class CollectionDebuggerView<T, U>
{
    // Fields
    private readonly ICollection<KeyValuePair<T, U>> c;

    // Methods
    public CollectionDebuggerView(ICollection<KeyValuePair<T, U>> col)
    {
        this.c = col;
    }

    // Properties
    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    public KeyValuePair<T, U>[] Items
    {
        get
        {
            KeyValuePair<T, U>[] array = new KeyValuePair<T, U>[this.c.Count];
            this.c.CopyTo(array, 0);
            return array;
        }
    }
}

/* 
 * Declare this outside the main class so it doesn't have to be inflated for each
 * instantiation of MapEx.
 */
internal struct Link
{
    public int HashCode;
    public int Next;
}

[ComVisible(false)]
[Serializable]
[DebuggerDisplay("Count={Count}")]
[DebuggerTypeProxy(typeof(CollectionDebuggerView<,>))]
public class Map<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, ISerializable, IDeserializationCallback
#if NET_4_5
        , IReadOnlyDictionary<TKey, TValue>
#endif
{
    // The implementation of this class uses a hash table and linked lists
    // (see: http://msdn2.microsoft.com/en-us/library/ms379571(VS.80).aspx).
    //      
    // We use a kind of "mini-heap" instead of reference-based linked lists:
    // "keySlots" and "valueSlots" is the heap itself, it stores the data
    // "linkSlots" contains information about how the slots in the heap
    //             are connected into linked lists
    //             In addition, the HashCode field can be used to check if the
    //             corresponding key and value are present (HashCode has the
    //             HASH_FLAG bit set in this case), so, to iterate over all the
    //             items in the mapContainer, simply iterate the linkSlots array
    //             and check for the HASH_FLAG bit in the HashCode field.
    //             For this reason, each time a hashcode is calculated, it needs
    //             to be ORed with HASH_FLAG before comparing it with the save hashcode.
    // "touchedSlots" and "emptySlot" manage the free space in the heap 

    const int INITIAL_SIZE = 10;
    const float DEFAULT_LOAD_FACTOR = (90f / 100);
    const int NO_SLOT = -1;
    const int HASH_FLAG = -2147483648;

    // The hash table contains indices into the linkSlots array
    int[] table;

    // All (key,value) pairs are chained into linked lists. The connection
    // information is stored in "linkSlots" along with the key's hash code
    // (for performance reasons).
    // TODO: get rid of the hash code in Link (this depends on a few
    // JIT-compiler optimizations)
    // Every link in "linkSlots" corresponds to the (key,value) pair
    // in "keySlots"/"valueSlots" with the same index.
    Link[] linkSlots;
    TKey[] keySlots;
    TValue[] valueSlots;

    //Leave those 2 fields here to improve heap layout.
    IEqualityComparer<TKey> hcp;
    SerializationInfo serialization_info;

    // The number of slots in "linkSlots" and "keySlots"/"valueSlots" that
    // are in use (i.e. filled with data) or have been used and marked as
    // "empty" later on.
    int touchedSlots;

    // The index of the first slot in the "empty slots chain".
    // "Remove()" prepends the cleared slots to the empty chain.
    // "Add()" fills the first slot in the empty slots chain with the
    // added item (or increases "touchedSlots" if the chain itself is empty).
    int emptySlot;

    // The number of (key,value) pairs in this mapContainer.
    int count;

    // The number of (key,value) pairs the mapContainer can hold without
    // resizing the hash table and the slots arrays.
    int threshold;

    // The number of changes made to this mapContainer. Used by enumerators
    // to detect changes and invalidate themselves.
    int generation;

    public int Count
    {
        get { return count; }
    }

    public TValue this[TKey key]
    {
        get
        {
            if (key == null)
                throw new ArgumentNullException("key");

            // get first item of linked list corresponding to given key
            int hashCode = hcp.GetHashCode(key) | HASH_FLAG;
            int cur = table[(hashCode & int.MaxValue) % table.Length] - 1;

            // walk linked list until right slot is found or end is reached 
            while (cur != NO_SLOT)
            {
                // The ordering is important for compatibility with MS and strange
                // Object.Equals () implementations
                if (linkSlots[cur].HashCode == hashCode && hcp.Equals(keySlots[cur], key))
                    return valueSlots[cur];
                cur = linkSlots[cur].Next;
            }
            throw new KeyNotFoundException();
        }

        set
        {
            if (key == null)
                throw new ArgumentNullException("key");

            // get first item of linked list corresponding to given key
            int hashCode = hcp.GetHashCode(key) | HASH_FLAG;
            int index = (hashCode & int.MaxValue) % table.Length;
            int cur = table[index] - 1;

            // walk linked list until right slot (and its predecessor) is
            // found or end is reached
            int prev = NO_SLOT;
            if (cur != NO_SLOT)
            {
                do
                {
                    // The ordering is important for compatibility with MS and strange
                    // Object.Equals () implementations
                    if (linkSlots[cur].HashCode == hashCode && hcp.Equals(keySlots[cur], key))
                        break;
                    prev = cur;
                    cur = linkSlots[cur].Next;
                } while (cur != NO_SLOT);
            }

            // is there no slot for the given key yet?              
            if (cur == NO_SLOT)
            {
                // there is no existing slot for the given key,
                // allocate one and prepend it to its corresponding linked
                // list

                if (++count > threshold)
                {
                    Resize();
                    index = (hashCode & int.MaxValue) % table.Length;
                }

                // find an empty slot
                cur = emptySlot;
                if (cur == NO_SLOT)
                    cur = touchedSlots++;
                else
                    emptySlot = linkSlots[cur].Next;

                // prepend the added item to its linked list,
                // update the hash table
                linkSlots[cur].Next = table[index] - 1;
                table[index] = cur + 1;

                // store the new item and its hash code
                linkSlots[cur].HashCode = hashCode;
                keySlots[cur] = key;
            }
            else
            {
                // we already have a slot for the given key,
                // update the existing slot     

                // if the slot is not at the front of its linked list,
                // we move it there
                if (prev != NO_SLOT)
                {
                    linkSlots[prev].Next = linkSlots[cur].Next;
                    linkSlots[cur].Next = table[index] - 1;
                    table[index] = cur + 1;
                }
            }

            // store the item's data itself
            valueSlots[cur] = value;

            generation++;
        }
    }

    public Map()
    {
        Init(INITIAL_SIZE, null);
    }

    public Map(IEqualityComparer<TKey> comparer)
    {
        Init(INITIAL_SIZE, comparer);
    }

    public Map(IDictionary<TKey, TValue> mapContainer)
        : this(mapContainer, null)
    {
    }

    public Map(int capacity)
    {
        Init(capacity, null);
    }

    public Map(IDictionary<TKey, TValue> mapContainer, IEqualityComparer<TKey> comparer)
    {
        if (mapContainer == null)
            throw new ArgumentNullException("mapContainer");
        int capacity = mapContainer.Count;
        Init(capacity, comparer);
        foreach (KeyValuePair<TKey, TValue> entry in mapContainer)
            this.Add(entry.Key, entry.Value);
    }

    public Map(int capacity, IEqualityComparer<TKey> comparer)
    {
        Init(capacity, comparer);
    }

    protected Map(SerializationInfo info, StreamingContext context)
    {
        serialization_info = info;
    }

    public Map(IList<TKey> keyList, IList<TValue> valList)
    {
        if (keyList.Count != valList.Count)
        {
            throw new Exception(
                "Key of the number not equal to value of the number");
        }

        Init(keyList.Count, null);

        int count = keyList.Count;
        for (int index = 0; index < count; ++index)
        {
            Add(keyList[index], valList[index]);
        }
    }

    public void Reset(int size)
    {
        Clear();
        if (size == 0)
            size = 1;
        InitArrays(size);
    }

    private void Init(int capacity, IEqualityComparer<TKey> hcp)
    {
        if (capacity < 0)
            throw new ArgumentOutOfRangeException("capacity");
        this.hcp = (hcp != null) ? hcp : EqualityComparer<TKey>.Default;
        //if (capacity == 0)
        //    capacity = INITIAL_SIZE;

        /* Modify capacity so 'capacity' elements can be added without resizing */
        capacity = (int)(capacity / DEFAULT_LOAD_FACTOR) + 1;

        InitArrays(capacity);
        generation = 0;
    }

    private void InitArrays(int size)
    {
        table = new int[size];

        linkSlots = new Link[size];
        emptySlot = NO_SLOT;

        keySlots = new TKey[size];
        valueSlots = new TValue[size];
        touchedSlots = 0;

        threshold = (int)(table.Length * DEFAULT_LOAD_FACTOR);
        if (threshold == 0 && table.Length > 0)
            threshold = 1;
    }

    void CopyToCheck(Array array, int index)
    {
        if (array == null)
            throw new ArgumentNullException("array");
        if (index < 0)
            throw new ArgumentOutOfRangeException("index");
        // we want no exception for index==array.Length && Count == 0
        if (index > array.Length)
            throw new ArgumentException("index larger than largest valid index of array");
        if (array.Length - index < Count)
            throw new ArgumentException("Destination array cannot hold the requested elements!");
    }

    void CopyKeys(TKey[] array, int index)
    {
        for (int i = 0; i < touchedSlots; i++)
        {
            if ((linkSlots[i].HashCode & HASH_FLAG) != 0)
                array[index++] = keySlots[i];
        }
    }

    void CopyValues(TValue[] array, int index)
    {
        for (int i = 0; i < touchedSlots; i++)
        {
            if ((linkSlots[i].HashCode & HASH_FLAG) != 0)
                array[index++] = valueSlots[i];
        }
    }

    delegate TRet Transform<TRet>(TKey key, TValue value);


    static KeyValuePair<TKey, TValue> make_pair(TKey key, TValue value)
    {
        return new KeyValuePair<TKey, TValue>(key, value);
    }

    static TKey pick_key(TKey key, TValue value)
    {
        return key;
    }

    static TValue pick_value(TKey key, TValue value)
    {
        return value;
    }

    void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
    {
        CopyToCheck(array, index);
        for (int i = 0; i < touchedSlots; i++)
        {
            if ((linkSlots[i].HashCode & HASH_FLAG) != 0)
                array[index++] = new KeyValuePair<TKey, TValue>(keySlots[i], valueSlots[i]);
        }
    }

    void Do_ICollectionCopyTo<TRet>(Array array, int index, Transform<TRet> transform)
    {
        Type src = typeof(TRet);
        Type tgt = array.GetType().GetElementType();

        try
        {
            if ((src.IsPrimitive || tgt.IsPrimitive) && !tgt.IsAssignableFrom(src))
                throw new Exception(); // we don't care.  it'll get transformed to an ArgumentException below

#if BOOTSTRAP_BASIC
                // BOOTSTRAP: gmcs 2.4.x seems to have trouble compiling the alternative
                throw new Exception ();
#else
            object[] dest = (object[])array;
            for (int i = 0; i < touchedSlots; i++)
            {
                if ((linkSlots[i].HashCode & HASH_FLAG) != 0)
                    dest[index++] = transform(keySlots[i], valueSlots[i]);
            }
#endif

        }
        catch (Exception e)
        {
            throw new ArgumentException("Cannot copy source collection elements to destination array", "array", e);
        }
    }

    private void Resize()
    {
        // From the SDK docs:
        //   Hashtable is automatically increased
        //   to the smallest prime number that is larger
        //   than twice the current number of Hashtable buckets
        int newSize = HashPrimeNumbers.ToPrime((table.Length << 1) | 1);

        // allocate new hash table and link slots array
        int[] newTable = new int[newSize];
        Link[] newLinkSlots = new Link[newSize];

        for (int i = 0; i < table.Length; i++)
        {
            int cur = table[i] - 1;
            while (cur != NO_SLOT)
            {
                int hashCode = newLinkSlots[cur].HashCode = hcp.GetHashCode(keySlots[cur]) | HASH_FLAG;
                int index = (hashCode & int.MaxValue) % newSize;
                newLinkSlots[cur].Next = newTable[index] - 1;
                newTable[index] = cur + 1;
                cur = linkSlots[cur].Next;
            }
        }
        table = newTable;
        linkSlots = newLinkSlots;

        // allocate new data slots, copy data
        TKey[] newKeySlots = new TKey[newSize];
        TValue[] newValueSlots = new TValue[newSize];
        Array.Copy(keySlots, 0, newKeySlots, 0, touchedSlots);
        Array.Copy(valueSlots, 0, newValueSlots, 0, touchedSlots);
        keySlots = newKeySlots;
        valueSlots = newValueSlots;

        threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
    }

    public void Add(TKey key, TValue value)
    {
        if (key == null)
            throw new ArgumentNullException("key");

        // get first item of linked list corresponding to given key
        int hashCode = hcp.GetHashCode(key) | HASH_FLAG;
        int index = (hashCode & int.MaxValue) % table.Length;
        int cur = table[index] - 1;

        // walk linked list until end is reached (throw an exception if a
        // existing slot is found having an equivalent key)
        while (cur != NO_SLOT)
        {
            // The ordering is important for compatibility with MS and strange
            // Object.Equals () implementations
            if (linkSlots[cur].HashCode == hashCode && hcp.Equals(keySlots[cur], key))
                throw new ArgumentException("An element with the same key already exists in the mapContainer.");
            cur = linkSlots[cur].Next;
        }

        if (++count > threshold)
        {
            Resize();
            index = (hashCode & int.MaxValue) % table.Length;
        }

        // find an empty slot
        cur = emptySlot;
        if (cur == NO_SLOT)
            cur = touchedSlots++;
        else
            emptySlot = linkSlots[cur].Next;

        // store the hash code of the added item,
        // prepend the added item to its linked list,
        // update the hash table
        linkSlots[cur].HashCode = hashCode;
        linkSlots[cur].Next = table[index] - 1;
        table[index] = cur + 1;

        // store item's data 
        keySlots[cur] = key;
        valueSlots[cur] = value;

        generation++;
    }

    public IEqualityComparer<TKey> Comparer
    {
        get { return hcp; }
    }

    public void Clear()
    {
        count = 0;
        // clear the hash table
        Array.Clear(table, 0, table.Length);
        // clear arrays
        Array.Clear(keySlots, 0, keySlots.Length);
        Array.Clear(valueSlots, 0, valueSlots.Length);
        Array.Clear(linkSlots, 0, linkSlots.Length);

        // empty the "empty slots chain"
        emptySlot = NO_SLOT;

        touchedSlots = 0;
        generation++;
    }

    public bool ContainsKey(TKey key)
    {
        if (key == null)
            throw new ArgumentNullException("key");

        // get first item of linked list corresponding to given key
        int hashCode = hcp.GetHashCode(key) | HASH_FLAG;
        int cur = table[(hashCode & int.MaxValue) % table.Length] - 1;

        // walk linked list until right slot is found or end is reached
        while (cur != NO_SLOT)
        {
            // The ordering is important for compatibility with MS and strange
            // Object.Equals () implementations
            if (linkSlots[cur].HashCode == hashCode && hcp.Equals(keySlots[cur], key))
                return true;
            cur = linkSlots[cur].Next;
        }

        return false;
    }

    public bool ContainsValue(TValue value)
    {
        IEqualityComparer<TValue> cmp = EqualityComparer<TValue>.Default;

        for (int i = 0; i < table.Length; i++)
        {
            int cur = table[i] - 1;
            while (cur != NO_SLOT)
            {
                if (cmp.Equals(valueSlots[cur], value))
                    return true;
                cur = linkSlots[cur].Next;
            }
        }
        return false;
    }

    //[SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
    public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        if (info == null)
            throw new ArgumentNullException("info");

        info.AddValue("Version", generation);
        info.AddValue("Comparer", hcp);
        // MS.NET expects either *no* KeyValuePairs field (when count = 0)
        // or a non-null KeyValuePairs field. We don't omit the field to
        // remain compatible with older monos, but we also doesn't serialize
        // it as null to make MS.NET happy.
        KeyValuePair<TKey, TValue>[] data = new KeyValuePair<TKey, TValue>[count];
        if (count > 0)
            CopyTo(data, 0);
        info.AddValue("HashSize", table.Length);
        info.AddValue("KeyValuePairs", data);
    }

    public virtual void OnDeserialization(object sender)
    {
        if (serialization_info == null)
            return;

        int hashSize = 0;
        KeyValuePair<TKey, TValue>[] data = null;

        // We must use the enumerator because MS.NET doesn't
        // serialize "KeyValuePairs" for count = 0.
        SerializationInfoEnumerator e = serialization_info.GetEnumerator();
        while (e.MoveNext())
        {
            switch (e.Name)
            {
                case "Version":
                    generation = (int)e.Value;
                    break;

                case "Comparer":
                    hcp = (IEqualityComparer<TKey>)e.Value;
                    break;

                case "HashSize":
                    hashSize = (int)e.Value;
                    break;

                case "KeyValuePairs":
                    data = (KeyValuePair<TKey, TValue>[])e.Value;
                    break;
            }
        }

        if (hcp == null)
            hcp = EqualityComparer<TKey>.Default;
        if (hashSize < INITIAL_SIZE)
            hashSize = INITIAL_SIZE;
        InitArrays(hashSize);
        count = 0;

        if (data != null)
        {
            for (int i = 0; i < data.Length; ++i)
                Add(data[i].Key, data[i].Value);
        }
        generation++;
        serialization_info = null;
    }

    public bool Remove(TKey key)
    {
        if (key == null)
            throw new ArgumentNullException("key");

        // get first item of linked list corresponding to given key
        int hashCode = hcp.GetHashCode(key) | HASH_FLAG;
        int index = (hashCode & int.MaxValue) % table.Length;
        int cur = table[index] - 1;

        // if there is no linked list, return false
        if (cur == NO_SLOT)
            return false;

        // walk linked list until right slot (and its predecessor) is
        // found or end is reached
        int prev = NO_SLOT;
        do
        {
            // The ordering is important for compatibility with MS and strange
            // Object.Equals () implementations
            if (linkSlots[cur].HashCode == hashCode && hcp.Equals(keySlots[cur], key))
                break;
            prev = cur;
            cur = linkSlots[cur].Next;
        } while (cur != NO_SLOT);

        // if we reached the end of the chain, return false
        if (cur == NO_SLOT)
            return false;

        count--;
        // remove slot from linked list
        // is slot at beginning of linked list?
        if (prev == NO_SLOT)
            table[index] = linkSlots[cur].Next + 1;
        else
            linkSlots[prev].Next = linkSlots[cur].Next;

        // mark slot as empty and prepend it to "empty slots chain"             
        linkSlots[cur].Next = emptySlot;
        emptySlot = cur;

        linkSlots[cur].HashCode = 0;
        // clear empty key and value slots
        keySlots[cur] = default(TKey);
        valueSlots[cur] = default(TValue);

        generation++;
        return true;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        if (key == null)
            throw new ArgumentNullException("key");

        // get first item of linked list corresponding to given key
        int hashCode = hcp.GetHashCode(key) | HASH_FLAG;
        int cur = table[(hashCode & int.MaxValue) % table.Length] - 1;

        // walk linked list until right slot is found or end is reached
        while (cur != NO_SLOT)
        {
            // The ordering is important for compatibility with MS and strange
            // Object.Equals () implementations
            if (linkSlots[cur].HashCode == hashCode && hcp.Equals(keySlots[cur], key))
            {
                value = valueSlots[cur];
                return true;
            }
            cur = linkSlots[cur].Next;
        }

        // we did not find the slot
        value = default(TValue);
        return false;
    }

    ICollection<TKey> IDictionary<TKey, TValue>.Keys
    {
        get { return Keys; }
    }

    ICollection<TValue> IDictionary<TKey, TValue>.Values
    {
        get { return Values; }
    }

#if NET_4_5
        IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys {
            get { return Keys; }
        }
  
        IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values {
            get { return Values; }
        }
#endif

    public KeyCollection Keys
    {
        get { return new KeyCollection(this); }
    }

    public ValueCollection Values
    {
        get { return new ValueCollection(this); }
    }

    ICollection IDictionary.Keys
    {
        get { return Keys; }
    }

    ICollection IDictionary.Values
    {
        get { return Values; }
    }

    bool IDictionary.IsFixedSize
    {
        get { return false; }
    }

    bool IDictionary.IsReadOnly
    {
        get { return false; }
    }

    static TKey ToTKey(object key)
    {
        if (key == null)
            throw new ArgumentNullException("key");
        if (!(key is TKey))
            throw new ArgumentException("not of type: " + typeof(TKey).ToString(), "key");
        return (TKey)key;
    }

    static TValue ToTValue(object value)
    {
        if (value == null && !typeof(TValue).IsValueType)
            return default(TValue);
        if (!(value is TValue))
            throw new ArgumentException("not of type: " + typeof(TValue).ToString(), "value");
        return (TValue)value;
    }

    object IDictionary.this[object key]
    {
        get
        {
            if (key is TKey && ContainsKey((TKey)key))
                return this[ToTKey(key)];
            return null;
        }
        set { this[ToTKey(key)] = ToTValue(value); }
    }

    void IDictionary.Add(object key, object value)
    {
        this.Add(ToTKey(key), ToTValue(value));
    }

    bool IDictionary.Contains(object key)
    {
        if (key == null)
            throw new ArgumentNullException("key");
        if (key is TKey)
            return ContainsKey((TKey)key);
        return false;
    }

    void IDictionary.Remove(object key)
    {
        if (key == null)
            throw new ArgumentNullException("key");
        if (key is TKey)
            Remove((TKey)key);
    }

    bool ICollection.IsSynchronized
    {
        get { return false; }
    }

    object ICollection.SyncRoot
    {
        get { return this; }
    }

    bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
    {
        get { return false; }
    }

    void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair)
    {
        Add(keyValuePair.Key, keyValuePair.Value);
    }

    bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair)
    {
        return ContainsKeyValuePair(keyValuePair);
    }

    void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
    {
        this.CopyTo(array, index);
    }

    bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair)
    {
        if (!ContainsKeyValuePair(keyValuePair))
            return false;

        return Remove(keyValuePair.Key);
    }

    bool ContainsKeyValuePair(KeyValuePair<TKey, TValue> pair)
    {
        TValue value;
        if (!TryGetValue(pair.Key, out value))
            return false;

        return EqualityComparer<TValue>.Default.Equals(pair.Value, value);
    }

    void ICollection.CopyTo(Array array, int index)
    {
        KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[];
        if (pairs != null)
        {
            this.CopyTo(pairs, index);
            return;
        }

        CopyToCheck(array, index);
        DictionaryEntry[] entries = array as DictionaryEntry[];
        if (entries != null)
        {
            for (int i = 0; i < touchedSlots; i++)
            {
                if ((linkSlots[i].HashCode & HASH_FLAG) != 0)
                    entries[index++] = new DictionaryEntry(keySlots[i], valueSlots[i]);
            }
            return;
        }

        Do_ICollectionCopyTo<KeyValuePair<TKey, TValue>>(array, index, make_pair);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new Enumerator(this);
    }

    IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
    {
        return new Enumerator(this);
    }

    IDictionaryEnumerator IDictionary.GetEnumerator()
    {
        return new ShimEnumerator(this);
    }

    public Enumerator GetEnumerator()
    {
        return new Enumerator(this);
    }

    int iteratorIndex = -1;
    bool iteratorState = false;

    public void Begin()
    {
        iteratorIndex = -1;
        iteratorState = true;
    }

    public bool Next()
    {
        if (iteratorIndex >= touchedSlots)
        {
            iteratorIndex = -1;
            iteratorState = false;
            return false;
        }

        while (++iteratorIndex < touchedSlots)
        {
            if ((linkSlots[iteratorIndex].HashCode & HASH_FLAG) != 0)
            {
                return true;
            }
        }

        iteratorIndex = -1;
        iteratorState = false;

        return false;
    }

    public TKey Key
    {
        get
        {
            if (!iteratorState)
            {
                throw new Exception("Key must access in iterator");
            }

            if (iteratorIndex < 0 || iteratorIndex >= touchedSlots)
            {
                throw new IndexOutOfRangeException("iterator invalid");
            }

            return keySlots[iteratorIndex];
        }
    }

    public TValue Value
    {
        get
        {
            if (!iteratorState)
            {
                throw new Exception("Value must access in iterator");
            }

            if (iteratorIndex < 0 || iteratorIndex >= touchedSlots)
            {
                throw new IndexOutOfRangeException("iterator invalid");
            }

            return valueSlots[iteratorIndex];
        }
    }

    [Serializable]
    private class ShimEnumerator : IDictionaryEnumerator, IEnumerator
    {
        Enumerator host_enumerator;
        public ShimEnumerator(Map<TKey, TValue> host)
        {
            host_enumerator = host.GetEnumerator();
        }

        public void Dispose()
        {
            host_enumerator.Dispose();
        }

        public bool MoveNext()
        {
            return host_enumerator.MoveNext();
        }

        public DictionaryEntry Entry
        {
            get { return ((IDictionaryEnumerator)host_enumerator).Entry; }
        }

        public object Key
        {
            get { return host_enumerator.Current.Key; }
        }

        public object Value
        {
            get { return host_enumerator.Current.Value; }
        }

        // This is the raison d' etre of this $%!@$%@^@ class.
        // We want: IDictionary.GetEnumerator ().Current is DictionaryEntry
        public object Current
        {
            get { return Entry; }
        }

        public void Reset()
        {
            host_enumerator.Reset();
        }
    }

    [Serializable]
    public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>,
        IDisposable, IDictionaryEnumerator, IEnumerator
    {
        Map<TKey, TValue> mapContainer;
        int next;
        int stamp;

        internal KeyValuePair<TKey, TValue> current;

        internal Enumerator(Map<TKey, TValue> mapContainer)
            : this()
        {
            this.mapContainer = mapContainer;
            stamp = mapContainer.generation;
        }

        public bool MoveNext()
        {
            VerifyState();

            if (next < 0)
                return false;

            while (next < mapContainer.touchedSlots)
            {
                int cur = next++;
                if ((mapContainer.linkSlots[cur].HashCode & HASH_FLAG) != 0)
                {
                    current = new KeyValuePair<TKey, TValue>(
                        mapContainer.keySlots[cur],
                        mapContainer.valueSlots[cur]
                        );
                    return true;
                }
            }

            next = -1;
            return false;
        }

        // No error checking happens.  Usually, Current is immediately preceded by a MoveNext(), so it's wasteful to check again
        public KeyValuePair<TKey, TValue> Current
        {
            get { return current; }
        }

        internal TKey CurrentKey
        {
            get
            {
                VerifyCurrent();
                return current.Key;
            }
        }

        internal TValue CurrentValue
        {
            get
            {
                VerifyCurrent();
                return current.Value;
            }
        }

        object IEnumerator.Current
        {
            get
            {
                VerifyCurrent();
                return current;
            }
        }

        void IEnumerator.Reset()
        {
            Reset();
        }

        internal void Reset()
        {
            VerifyState();
            next = 0;
        }

        DictionaryEntry IDictionaryEnumerator.Entry
        {
            get
            {
                VerifyCurrent();
                return new DictionaryEntry(current.Key, current.Value);
            }
        }

        object IDictionaryEnumerator.Key
        {
            get { return CurrentKey; }
        }

        object IDictionaryEnumerator.Value
        {
            get { return CurrentValue; }
        }

        void VerifyState()
        {
            if (mapContainer == null)
                throw new ObjectDisposedException(null);
            if (mapContainer.generation != stamp)
                throw new InvalidOperationException("out of sync");
        }

        void VerifyCurrent()
        {
            VerifyState();
            if (next <= 0)
                throw new InvalidOperationException("Current is not valid");
        }

        public void Dispose()
        {
            mapContainer = null;
        }
    }

    // This collection is a read only collection
    [Serializable]
    [DebuggerDisplay("Count={Count}")]
    [DebuggerTypeProxy(typeof(CollectionDebuggerView<,>))]
    public sealed class KeyCollection : ICollection<TKey>, IEnumerable<TKey>, ICollection, IEnumerable
    {
        Map<TKey, TValue> mapContainer;

        public KeyCollection(Map<TKey, TValue> mapContainer)
        {
            if (mapContainer == null)
                throw new ArgumentNullException("mapContainer");
            this.mapContainer = mapContainer;
        }


        public void CopyTo(TKey[] array, int index)
        {
            mapContainer.CopyToCheck(array, index);
            mapContainer.CopyKeys(array, index);
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(mapContainer);
        }

        void ICollection<TKey>.Add(TKey item)
        {
            throw new NotSupportedException("this is a read-only collection");
        }

        void ICollection<TKey>.Clear()
        {
            throw new NotSupportedException("this is a read-only collection");
        }

        bool ICollection<TKey>.Contains(TKey item)
        {
            return mapContainer.ContainsKey(item);
        }

        bool ICollection<TKey>.Remove(TKey item)
        {
            throw new NotSupportedException("this is a read-only collection");
        }

        IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        void ICollection.CopyTo(Array array, int index)
        {
            var target = array as TKey[];
            if (target != null)
            {
                CopyTo(target, index);
                return;
            }

            mapContainer.CopyToCheck(array, index);
            mapContainer.Do_ICollectionCopyTo<TKey>(array, index, pick_key);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public int Count
        {
            get { return mapContainer.Count; }
        }

        bool ICollection<TKey>.IsReadOnly
        {
            get { return true; }
        }

        bool ICollection.IsSynchronized
        {
            get { return false; }
        }

        object ICollection.SyncRoot
        {
            get { return ((ICollection)mapContainer).SyncRoot; }
        }

        [Serializable]
        public struct Enumerator : IEnumerator<TKey>, IDisposable, IEnumerator
        {
            Map<TKey, TValue>.Enumerator host_enumerator;

            internal Enumerator(Map<TKey, TValue> host)
            {
                host_enumerator = host.GetEnumerator();
            }

            public void Dispose()
            {
                host_enumerator.Dispose();
            }

            public bool MoveNext()
            {
                return host_enumerator.MoveNext();
            }

            public TKey Current
            {
                get { return host_enumerator.current.Key; }
            }

            object IEnumerator.Current
            {
                get { return host_enumerator.CurrentKey; }
            }

            void IEnumerator.Reset()
            {
                host_enumerator.Reset();
            }
        }
    }

    // This collection is a read only collection
    [Serializable]
    [DebuggerDisplay("Count={Count}")]
    [DebuggerTypeProxy(typeof(CollectionDebuggerView<,>))]
    public sealed class ValueCollection : ICollection<TValue>, IEnumerable<TValue>, ICollection, IEnumerable
    {
        Map<TKey, TValue> mapContainer;

        public ValueCollection(Map<TKey, TValue> mapContainer)
        {
            if (mapContainer == null)
                throw new ArgumentNullException("mapContainer");
            this.mapContainer = mapContainer;
        }

        public void CopyTo(TValue[] array, int index)
        {
            mapContainer.CopyToCheck(array, index);
            mapContainer.CopyValues(array, index);
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(mapContainer);
        }

        void ICollection<TValue>.Add(TValue item)
        {
            throw new NotSupportedException("this is a read-only collection");
        }

        void ICollection<TValue>.Clear()
        {
            throw new NotSupportedException("this is a read-only collection");
        }

        bool ICollection<TValue>.Contains(TValue item)
        {
            return mapContainer.ContainsValue(item);
        }

        bool ICollection<TValue>.Remove(TValue item)
        {
            throw new NotSupportedException("this is a read-only collection");
        }

        IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        void ICollection.CopyTo(Array array, int index)
        {
            var target = array as TValue[];
            if (target != null)
            {
                CopyTo(target, index);
                return;
            }

            mapContainer.CopyToCheck(array, index);
            mapContainer.Do_ICollectionCopyTo<TValue>(array, index, pick_value);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public int Count
        {
            get { return mapContainer.Count; }
        }

        bool ICollection<TValue>.IsReadOnly
        {
            get { return true; }
        }

        bool ICollection.IsSynchronized
        {
            get { return false; }
        }

        object ICollection.SyncRoot
        {
            get { return ((ICollection)mapContainer).SyncRoot; }
        }

        [Serializable]
        public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator
        {
            Map<TKey, TValue>.Enumerator host_enumerator;

            internal Enumerator(Map<TKey, TValue> host)
            {
                host_enumerator = host.GetEnumerator();
            }

            public void Dispose()
            {
                host_enumerator.Dispose();
            }

            public bool MoveNext()
            {
                return host_enumerator.MoveNext();
            }

            public TValue Current
            {
                get { return host_enumerator.current.Value; }
            }

            object IEnumerator.Current
            {
                get { return host_enumerator.CurrentValue; }
            }

            void IEnumerator.Reset()
            {
                host_enumerator.Reset();
            }
        }
    }
}